package swardToOffer.method_4_dp_or_greedy;

import java.util.HashMap;
import java.util.HashSet;

/**
 * @Author ChanZany
 * @Date 2021/5/25 10:38
 * @Version 1.0
 * 面试题48：最长不含重复字符的子字符串
 * 题目：请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子
 * 字符串的长度。假设字符串中只包含从'a'到'z'的字符。
 * 解法:
 * 1. 动态规划+哈希表
 * 定义f(j)为前j个字符组成的字符串中最长子字符串的长度
 * 定义s[i]==s[j],i<j,即前j个字符中和当前字符重复的下标(通过HashMap记录)
 * 如s=abca中,
 * 当j=3时,s[0]=s[j],i=0,j-i=3,f(j)=j-i
 * 当j=2时,前面没有重复字符出现,所以下标置为i=-1,j-i=3,f(j)=f(j-1)+1
 * 由此可以得到状态转移方程:
 * f(j) = f(j-1)+1; f(j-1)<j-i
 * f(j) = f(j-1); f(j-1)>=j-i
 * 由于f(j)之和f(j-1)有关,所以用tmp变量来存储dp
 * 2. 双指针+set
 */
public class LongestSubstringWithoutDup {
    public int lengthOfLongestSubstring(String s) {
        char[] charArray = s.toCharArray();
        int res = 0, tmp = 0;
        HashMap<Character, Integer> map = new HashMap<>();
        for (int j = 0; j < charArray.length; j++) {
            Integer i = map.getOrDefault(charArray[j], -1);
            map.put(charArray[j], j);
            tmp = tmp < j - i ? tmp + 1 : j - i;
            res = Math.max(res, tmp);
        }
        return res;
    }

    public int lengthOfLongestSubstring2(String s) {
        int res = 0,right=0;
        HashSet<Character> set = new HashSet<>();
        //i为左指针
        for (int i = 0; i < s.length(); i++) {
            //移动左指针，并删除上一个元素
            if(i!=0){
                set.remove(s.charAt(i-1));
            }
            //i不动,一直右移right指针直到出现重复的数
            while (right<s.length() && !set.contains(s.charAt(right))){
                set.add(s.charAt(right));
                right++;
            }
            res = Math.max(res,right-i);

        }
        return res;

    }


    public static void main(String[] args) {
        LongestSubstringWithoutDup Main = new LongestSubstringWithoutDup();
        System.out.println(Main.lengthOfLongestSubstring("abbddeadqwerd"));
        System.out.println(Main.lengthOfLongestSubstring2("abbddeadqwerd"));
    }
}
